#include <stdio.h>
#include <stdlib.h>

typedef struct Link_Stack Link_Stack_t;
typedef struct Link_Stack* pLink_Stack_t;
typedef struct Stack_Node Stack_Node_t;
typedef struct Stack_Node* pStack_Node_t;


//管理栈的结构体
struct Link_Stack
{
    //栈元素多少
    int size;
    //栈入口
    struct Stack_Node *top;
};

//栈元素节点
struct Stack_Node
{
    //栈元素值
    int data;
    //指向下一个栈
    struct Stack_Node *next;
};

//栈初始化函数(！！！不是栈元素初始函数)
pLink_Stack_t Init_Link_Stack( void )
{
    //给管理栈的结构体申请一个堆空间用于管理栈
    pLink_Stack_t plink_stack =( pLink_Stack_t)malloc( sizeof( Link_Stack_t ) );
    if ( plink_stack == NULL )
    {
        perror( "malloc stack fail" );
        return NULL;
    }
    //给栈初始化
    plink_stack->size = 0;
    plink_stack->top = NULL;
    
    //返回栈的地址
    return plink_stack;
}

//压栈/入栈
void Push_stack( pLink_Stack_t plink_stack,int data )
{
    pStack_Node_t pnew = ( pStack_Node_t )malloc( sizeof( pStack_Node_t ) );
    if( pnew == NULL)
    {
        perror( "malloc a stack node fail\n" );
        return ;
    }

    //栈中无元素时
    if( plink_stack->top == NULL)
    {
        //给栈元素赋值
        pnew->data = data;
        pnew->next = NULL;
        //将首个栈节点放进栈里
        plink_stack->top = pnew;
        plink_stack->size++;
        return ;
    }
    //普通情况的压栈,相当于链表的头插法
    //先处理自己，再处理别人
    //先自己
    pnew->data = data;
    pnew->next = plink_stack->top;
    //后别人
    plink_stack->top = pnew;
    plink_stack->size++;
    return ;
}

void Print_Stack( pLink_Stack_t plink_stack )
{
    if(plink_stack->top == NULL)
    {
        printf( "None element in stack\n" );
        return ;
    }
    
    pStack_Node_t pstack_node = plink_stack->top;
    printf("栈顶-> ");
    while( pstack_node != NULL )
    {
        printf( "%d ",pstack_node->data );
        pstack_node=pstack_node->next;
    }
    printf( "<-栈底" );
    printf("\n");
    return ;
}

//出栈函数
void Pop_Stack( pLink_Stack_t plink_stack ){
    //空栈
    if( plink_stack->top == NULL)
    {
        perror( "None element in stack" );
        return ;
    }
    //普通情况
    pStack_Node_t pstack_node = plink_stack->top;
    //ptemp存下一个pstack_node指向的
    //pStack_Node_t ptemp = pstack_node->next;

    //出栈，栈的首元素先出
    //将栈的top指针指向第二个节点
    plink_stack->top = pstack_node->next;
    free( pstack_node );
    plink_stack->size--;
    return;
   
}

int Pop_and_get_Stack( pLink_Stack_t plink_stack ){
    //空栈
    if( plink_stack->size == 0)
    {
        perror( "None element in stack" );
        return -1;
    }
   
    pStack_Node_t pstack_node = plink_stack->top;
    int data = pstack_node->data;

    //出栈，栈的首元素先出
    //将栈的top指针指向第二个节点
    plink_stack->top = pstack_node->next;
    free( pstack_node );
    plink_stack->size--;
    return data;
   
}

//销毁栈
void Destroy_Stack( pLink_Stack_t plink_stack )
{
    if( plink_stack == NULL )
    {
        printf( "plink_stack is NULL\n" );
        return ;
    }
    
    pStack_Node_t pstack_node = plink_stack->top;
    //保存pstack_node的下一个栈元素
    pStack_Node_t ptemp=NULL;

    while( pstack_node != NULL )
    {
        ptemp = pstack_node->next;
        free( pstack_node );
        plink_stack->top = ptemp;
        pstack_node = ptemp;
    }
    free( plink_stack );
    printf( "栈销毁成功\n" );
    return ;
}


int main()
{   
    //接收栈的信息
    pLink_Stack_t plink_stack = Init_Link_Stack();
    
    //压栈
    #if 1
    Push_stack( plink_stack,1 );
    Push_stack( plink_stack,2 );
    Push_stack( plink_stack,3 );
    Push_stack( plink_stack,4 );
    Push_stack( plink_stack,5 );
    #endif

    //出栈
    #if 0
    Pop_Stack(plink_stack);
    Pop_Stack(plink_stack);
    Pop_Stack(plink_stack);
    Pop_Stack(plink_stack);
    #endif

    //获取出栈的数据
    #if 1
    while( plink_stack->size != 0 )
    {
        int data = Pop_and_get_Stack( plink_stack );
        printf( "data = %d\n",data );
    }
    #endif

    Print_Stack( plink_stack );
    Destroy_Stack( plink_stack );
    plink_stack = NULL;

   

    return 0;
}